package com.atguigu.srb.base.algorithm;


class Solution2 {


    public static int searchInsert(int a, int[] arr) {
        if (arr.length == 1) {
            int c = arr[0];
            if (c == a || c > a) {
                return 0;
            } else {
                return 1;
            }
        }
        int start = 0;
        int end = arr.length - 1;
        while (arr[start] <= arr[end]) {
            if (a < arr[start]) {
                return 0;
            }
            if (a > arr[end]) {
                return arr.length;
            }
            int mid = (end - start + 1) / 2 + start;
            if (a == arr[mid]) {
                return mid;
            } else if (a > arr[mid]) {
                start = mid;
            } else if (a < arr[mid]) {
                end = mid;
            }
            if (a > arr[mid] && a < arr[mid + 1]) {
                return mid + 1;
            }
            if (a < arr[mid] && a > arr[mid - 1]) {
                return mid;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 3, 4, 7,8,9,11,22,43,56,78,89,111,222,444,555};
        int[] arr2 = new int[]{4};
        long start = System.currentTimeMillis();
        int index = searchInsert(2, arr1);
        long end =  System.currentTimeMillis();
        System.out.println(index);
        System.out.println(end - start);
    }
}

